﻿using System;
using System.Collections.Generic;
using System.Data;

namespace PathFind.Algo {
    /// <summary>
    /// 最小堆
    /// </summary>
    /// <typeparam name="TNode"></typeparam>
    public class BinaryHeap<TNode> where TNode: Node {
        private List<TNode> _heap;
        public BinaryHeap() {
            _heap = new List<TNode>();
        }

        public void Insert(in TNode node) {
            _heap.Add(node);
            _shiftUp(_heap.Count - 1);
        }

        /// <summary>
        /// 只有当栈中元素存在,且小于 node.Total时,才将node插入栈中
        /// 插入成功时,返回true,否则为false
        /// </summary>
        /// <param name="node"></param>
        /// <returns></returns>
        public bool InsertSmaller(TNode node) {
            for (int i = 0; i < _heap.Count; i++) {
                if (node.pos == _heap[i].pos) {
                    if (node.Total < _heap[i].Total) {
                        _heap[i] = node;
                        _shiftUp(i);
                        return true;
                    }

                    return false;
                }
            }
            return false;
        }

        public TNode PopMin() {
            if (_heap.Count <= 0) {
                throw new DataException("Empty heap! Please check before you pop!");
            }
            var result = _heap[0];
            var heapLastIndex = _heap.Count - 1;
            _heap[0] = _heap[heapLastIndex];
            _heap.RemoveAt(heapLastIndex);
            _shiftDown(0);
            return result;
        }

        public int Count() {
            return _heap.Count;
        }

        public void Clear() {
            _heap.Clear();
        }

        public bool HasSmallerElement(TNode node) {
            var total = node.Total;
            for (int i = 0; i < _heap.Count; i++) {
                if (_heap[i].Total < total) {
                    return true;
                }
            }
            return false;
        }

        int GetHeapCapacity() {
            return _heap.Capacity;
        }

        private void _buildHeap() {
            for (int i = _heap.Count>>1; i >= 0; --i){
                _shiftDown(i);
            }
        }

        private void _shiftDown(int i) {
            int leftChild = (i << 1) + 1;
            int rightChild = (i << 1) + 2;

            int replace = i;
            if (rightChild < _heap.Count) {
                var leftTotal = _heap[leftChild].Total;
                var rightTotal = _heap[rightChild].Total;
                var iTotal = _heap[i].Total;
                bool leftLessRight = leftTotal < rightTotal;
                if (leftLessRight && leftTotal < iTotal ) {
                    replace = leftChild;
                }
                else if (!leftLessRight && rightTotal < iTotal ) {
                    replace = rightChild;
                }
            }
            else if (leftChild < _heap.Count) {
                if (_heap[i].Total > _heap[leftChild].Total) {
                    replace = leftChild;
                }
            }

            if (replace == i) {
                return;
            }

            (_heap[i], _heap[replace]) = (_heap[replace], _heap[i]);
            _shiftDown(replace);
        }

        private void _shiftUp(int i) {
            if (i == 0) {
                return;
            }
            var parent = (i - 1) >> 1;
            if (_heap[i].Total > _heap[parent].Total) {
                return;
            }
            (_heap[i], _heap[parent]) = (_heap[parent], _heap[i]);
            _shiftUp(parent);
        }
    }
}
